package com.dbh.company.util;

import cn.hutool.core.convert.Convert;

import java.awt.geom.Point2D;
import java.util.*;


/**
 * 坐标处理类 GPS点的抽稀-道格拉斯算法
 *
 * @author Elinx
 * @since 2021-05-31 10:28
 */
public class GisDouglasUtil {

    /**
     * 计算两点距离
     *
     * @param point1 点1
     * @param point2 点2
     * @return double
     */
    public static double calculationDistance(double[] point1, double[] point2) {
        double lat1 = point1[0];
        double lat2 = point2[0];
        double lng1 = point1[1];
        double lng2 = point2[1];
        double radLat1 = lat1 * Math.PI / 180.0;
        double radLat2 = lat2 * Math.PI / 180.0;
        double a = radLat1 - radLat2;
        double b = (lng1 * Math.PI / 180.0) - (lng2 * Math.PI / 180.0);
        double s = 2 * Math.asin(Math.sqrt(Math.pow(Math.sin(a / 2), 2)
                + Math.cos(radLat1) * Math.cos(radLat2) * Math.pow(Math.sin(b / 2), 2)));
        return s * 6370996.81;

    }

    /**
     * 计算点pX到点pA和pB所确定的直线的距离
     *
     * @param start  开始
     * @param end    结束
     * @param center 中心
     * @return double
     */
    private static double distToSegment(double[] start, double[] end, double[] center) {
        double a = Math.abs(calculationDistance(start, end));
        double b = Math.abs(calculationDistance(start, center));
        double c = Math.abs(calculationDistance(end, center));
        double p = (a + b + c) / 2.0;
        double s = Math.sqrt(Math.abs(p * (p - a) * (p - b) * (p - c)));
        return s * 2.0 / a;
    }

    /**
     * 递归方式压缩轨迹
     *
     * @param coordinate 坐标集
     * @param result     结果集
     * @param start      开始
     * @param end        结束
     * @param dMax       抽稀力度
     * @return List<double [ ]>
     */
    private static List<double[]> compressLine(List<double[]> coordinate, List<double[]> result, int start, int end, int dMax) {
        if (start < end) {
            double maxDist = 0;
            int currentIndex = 0;
            double[] startPoint = coordinate.get(start);
            double[] endPoint = coordinate.get(end);
            for (int i = start + 1; i < end; i++) {
                double currentDist = distToSegment(startPoint, endPoint, coordinate.get(i));
                if (currentDist > maxDist) {
                    maxDist = currentDist;
                    currentIndex = i;
                }
            }
            if (maxDist >= dMax) {
                //将当前点加入到过滤数组中
                result.add(coordinate.get(currentIndex));
                //将原来的线段以当前点为中心拆成两段，分别进行递归处理
                compressLine(coordinate, result, start, currentIndex, dMax);
                compressLine(coordinate, result, currentIndex, end, dMax);
            }
        }
        return result;
    }

    /**
     * @param coordinate 原始轨迹Array<{longitude, latitude}>
     * @param dMax       允许最大距离误差
     * @return douglasResult 抽稀后的轨迹
     */
    public static List<double[]> douglasPeucker(List<double[]> coordinate, int dMax) {
        //抽稀点数量需要大于2
        if (coordinate == null || coordinate.size() <= 2) {
            return null;
        }

        List<double[]> coordinate2 = new ArrayList<>();
        for (int i = 0; i < coordinate.size(); i++) {
            double[] point = Arrays.copyOf(coordinate.get(i), 3);
            point[2] = i;
            coordinate2.add(point);
        }
        List<double[]> result = new ArrayList<>();
        result = compressLine(coordinate2, result, 0, coordinate2.size() - 1, dMax);

        result.add(coordinate2.get(0));
        result.add(coordinate2.get(coordinate.size() - 1));

        Collections.sort(result, new Comparator<double[]>() {
            @Override
            public int compare(double[] u1, double[] u2) {
                if (u1[2] > u2[2]) {
                    return 1;
                } else if (u1[2] < u2[2]) {
                    return -1;
                }
                return 0; //相等为0
            }
        });

        return result;
    }


    private static double EARTH_RADIUS = 6378137;
    //private static double EARTH_SEA = 1.852;海里

    private static double rad(double d) {
        return d * Math.PI / 180.0;
    }

    /**
     * 判断是否在多边形区域内
     *
     * @param pointLon 要判断的点的横坐标 经度
     * @param pointLat 要判断的点的纵坐标 维度
     * @param lon      区域各顶点的横坐标数组
     * @param lat      区域各顶点的纵坐标数组
     * @return
     */
    public static boolean isInPolygon(double pointLon, double pointLat, Double[] lon,
                                      Double[] lat) {
        // 将要判断的横纵坐标组成一个点
        Point2D.Double point = new Point2D.Double(pointLon, pointLat);
        // 将区域各顶点的横纵坐标放到一个点集合里面
        List<Point2D.Double> pointList = new ArrayList<Point2D.Double>();
        double polygonPoint_x = 0.0, polygonPoint_y = 0.0;
        for (int i = 0; i < lon.length; i++) {
            polygonPoint_x = lon[i];
            polygonPoint_y = lat[i];
            Point2D.Double polygonPoint = new Point2D.Double(polygonPoint_x, polygonPoint_y);
            pointList.add(polygonPoint);
        }
        return check(point, pointList);
    }

    /**
     * @param point   要判断的点的横纵坐标
     * @param polygon 组成的顶点坐标集合
     * @return
     */
    private static boolean check(Point2D.Double point, List<Point2D.Double> polygon) {
        java.awt.geom.GeneralPath peneralPath = new java.awt.geom.GeneralPath();

        Point2D.Double first = polygon.get(0);
        // 通过移动到指定坐标（以双精度指定），将一个点添加到路径中
        peneralPath.moveTo(first.x, first.y);
        polygon.remove(0);
        for (Point2D.Double d : polygon) {
            // 通过绘制一条从当前坐标到新指定坐标（以双精度指定）的直线，将一个点添加到路径中。
            peneralPath.lineTo(d.x, d.y);
        }
        // 将几何多边形封闭
        peneralPath.lineTo(first.x, first.y);
        peneralPath.closePath();
        // 测试指定的 Point2D 是否在 Shape 的边界内。
        return peneralPath.contains(point);
    }

    /**
     * 返回一个点是否在一个多边形区域内， 如果点位于多边形的顶点或边上，不算做点在多边形内，返回false
     * @param point
     * @param polygon
     * @return
     */
    public static boolean checkWithJdkGeneralPath(Point2D.Double point, List<Point2D.Double> polygon) {
        java.awt.geom.GeneralPath p = new java.awt.geom.GeneralPath();
        Point2D.Double first = polygon.get(0);
        p.moveTo(first.x, first.y);
        polygon.remove(0);
        for (Point2D.Double d : polygon) {
            p.lineTo(d.x, d.y);
        }
        p.lineTo(first.x, first.y);
        p.closePath();
        return p.contains(point);
    }


    /**
     * 判断点是否在多边形内，如果点位于多边形的顶点或边上，也算做点在多边形内，直接返回true
     * @param point 检测点
     * @param pts   多边形的顶点
     * @return      点在多边形内返回true,否则返回false
     */
    public static boolean isPtInPoly(Point2D.Double point, List<Point2D.Double> pts){

        int N = pts.size();
        boolean boundOrVertex = true; //如果点位于多边形的顶点或边上，也算做点在多边形内，直接返回true
        int intersectCount = 0;//cross points count of x
        double precision = 2e-10; //浮点类型计算时候与0比较时候的容差
        Point2D.Double p1, p2;//neighbour bound vertices
        Point2D.Double p = point; //当前点

        p1 = pts.get(0);//left vertex
        for(int i = 1; i <= N; ++i){//check all rays
            if(p.equals(p1)){
                return boundOrVertex;//p is an vertex
            }

            p2 = pts.get(i % N);//right vertex
            if(p.x < Math.min(p1.x, p2.x) || p.x > Math.max(p1.x, p2.x)){//ray is outside of our interests
                p1 = p2;
                continue;//next ray left point
            }

            if(p.x > Math.min(p1.x, p2.x) && p.x < Math.max(p1.x, p2.x)){//ray is crossing over by the algorithm (common part of)
                if(p.y <= Math.max(p1.y, p2.y)){//x is before of ray
                    if(p1.x == p2.x && p.y >= Math.min(p1.y, p2.y)){//overlies on a horizontal ray
                        return boundOrVertex;
                    }

                    if(p1.y == p2.y){//ray is vertical
                        if(p1.y == p.y){//overlies on a vertical ray
                            return boundOrVertex;
                        }else{//before ray
                            ++intersectCount;
                        }
                    }else{//cross point on the left side
                        double xinters = (p.x - p1.x) * (p2.y - p1.y) / (p2.x - p1.x) + p1.y;//cross point of y
                        if(Math.abs(p.y - xinters) < precision){//overlies on a ray
                            return boundOrVertex;
                        }

                        if(p.y < xinters){//before ray
                            ++intersectCount;
                        }
                    }
                }
            }else{//special case when ray is crossing through the vertex
                if(p.x == p2.x && p.y <= p2.y){//p crossing over p2
                    Point2D.Double p3 = pts.get((i+1) % N); //next vertex
                    if(p.x >= Math.min(p1.x, p3.x) && p.x <= Math.max(p1.x, p3.x)){//p.x lies between p1.x & p3.x
                        ++intersectCount;
                    }else{
                        intersectCount += 2;
                    }
                }
            }
            p1 = p2;//next ray left point
        }

        if(intersectCount % 2 == 0){//偶数在多边形外
            return false;
        } else { //奇数在多边形内
            return true;
        }
    }

    /**
     * 通过经纬度获取距离(单位：米)
     *
     * @param lat1 纬度1
     * @param lng1 经度1
     * @param lat2 纬度2
     * @param lng2 经度2
     * @return 距离
     */
    public static double getDistance(double lat1, double lng1, double lat2,
                                     double lng2) {
        double radLat1 = rad(lat1);
        double radLat2 = rad(lat2);
        double a = radLat1 - radLat2;
        double b = rad(lng1) - rad(lng2);
        double s = 2 * Math.asin(Math.sqrt(Math.pow(Math.sin(a / 2), 2) +
                Math.cos(radLat1) * Math.cos(radLat2) * Math.pow(Math.sin(b / 2), 2)));
        s = s * EARTH_RADIUS;
        s = Math.round(s * 10000d) / 10000d;
        //double len=s/EARTH_SEA;
        //s = s / 1000;
        return s;
    }

    /**
     * @param lat1   纬度
     * @param lat2   纬度
     * @param lng1   经度
     * @param lng2   经度
     * @param radius 判断一个点是否在圆形区域内,比较坐标点与圆心的距离是否小于半径
     */
    public static boolean isInCircle(double lng1, double lat1, double lng2, double lat2, double radius) {
        double distance = getDistance(lat1, lng1, lat2, lng2);
        if (distance > radius) {
            return false;
        } else {
            //System.err.println("经度："+lng1+"维度："+lat1+"经度："+lng2+"维度："+lat2+"距离:"+distance);
            return true;
        }
    }

    public static void main(String[] args) {
        String str = "116.46606392545,39.972566307226;116.46632443405,39.972932628236;116.46683646819,39.972960275024;" +
                "116.46625256961,39.973250565621;116.46664782403,39.977093343072;116.46655799348,39.979063027656;" +
                "116.46652206126,39.979194337926;116.46744731594,39.970278484069;116.46760002787,39.972296748992;" +
                "116.467294604,39.973188360598;116.46720477345,39.973340417221;116.46731257011,39.973430268702;" +
                "116.46715985817,39.974169810981;116.46713290901,39.976568084185;116.4676539262,39.976644108749;" +
                "116.46762697704,39.976740867162;116.46716884123,39.977031141574;116.46821985867,39.972891158032;" +
                "116.46872290976,39.977715354912;116.46902833363,39.972282925464;116.46907324891,39.9723313078;" +
                "116.46917206251,39.975344768107;116.46973799499,39.973713645668;116.46977392721,39.974411715583;" +
                "116.46971104582,39.974778026623;116.4694954525,39.975593579945;116.47051053772,39.975800922445;" +
                "116.47049257161,39.9764160348;116.47075308021,39.978772761944;116.47127409741,39.978869517319;" +
                "116.47127409741,39.980044393001;116.47137291101,39.978710561987;116.47164240267,39.978710561987;116.47174121627,39.979325647943;116.47218138597,39.974971548638;116.47279223372,39.97826133838;116.47218138597,39.978558517407;116.47258562345,39.978855695131;116.47268443706,39.979698843443;116.47386121728,39.979228893219;116.47387918339,39.975946061818;116.47419359032,39.976436768827;116.47446308197,39.978593073023;116.47461579391,39.97680998023;116.47467867529,39.978033269871;116.47494816694,39.979201248986;116.47493918389,39.979926906349;116.4752176586,39.980258632842;116.47537037053,39.980355386096;116.47553206553,39.980707843214;116.47616986244,39.980051303974;116.47604409967,39.980196434248;116.47598121828,39.980410673609;116.47614291327,39.977273035967;116.47790359207,39.980099680767;116.47814613456,39.981903419391;116.47890969424,39.981979437972;116.47885579591,39.979650466365;116.47968223698,39.978288982996;116.48058054249,39.981011922391;116.47946664366,39.974688176928;116.47956545727,39.974895522198;116.4799786778,39.977570219326;116.47988884725,39.978109292793;116.48105664441,39.980839150299;116.48047274583,39.97743199467;116.48075122054,39.977542574418;116.48194596687,39.9811916049;116.48182918715,39.98126762428;116.48188308548,39.981751381972;116.48326647597,39.980915170074;116.482619696,39.981226159174;116.48392223899,39.981509503558;116.48477562922,39.981378197771;116.48566495168,39.97997528323;116.48563800251,39.981129407163;116.48595240944,39.981937973302;116.48677885051,39.981917240957;116.48741664742,39.981626987467;116.48587156195,39.976457502848;116.48574579917,39.976899827113;116.48802749517,39.98164080909;116.48818020711,39.981772114367;116.48906952956,39.982269689954;116.48297003515,39.96781777845;116.48669800301,39.976277807791;116.48721902021,39.9764160348;116.48911444484,39.981668452327;116.48939291954,39.98176520357;116.48985105535,39.981868865462;116.48654529108,39.973644529444;116.48708427438,39.975054486475;116.4875603763,39.975310210835;116.48783885101,39.976644108749;116.48810834267,39.977590953001;116.4895815637,39.979104494084;116.49030919116,39.980680199584;116.49053376754,39.981053387628;116.49016546228,39.981184694043;116.49029122505,39.981716827966;116.49014749617,39.981903419391;116.49062359809,39.9821452964;116.4905427506,39.982193671698;116.48709325744,39.973692910808;116.48715613882,39.973803496654;116.48714715577,39.974086872061;116.48789274934,39.975178893041;116.48883597013,39.976865270634;116.48971630953,39.978199137954;116.48986902146,39.979443135637;116.49023732672,39.97954680108;116.48801851211,39.97388643592;116.48918630928,39.975787099632;116.49000376729,39.974999194595;116.48849461403,39.97019554039;116.48848563098,39.970907470334;116.48853952931,39.971197769719;116.48905156345,39.972054836845;116.49029122505,39.973927905515;116.49055173365,39.974390980936;116.49100986946,39.974356423178;116.49019241145,39.972172337138;116.49035410644,39.972248366632;116.49088410669,39.973340417221;116.4911625814,39.973851877905;116.49140512389,39.973934817112;116.49083919142,39.971847482888;116.49114461529,39.971909689142;116.49135122556,39.972994833494;116.49233936162,39.971785276578;116.49188122581,39.972027189687;116.49190817497,39.972186160689;116.49224953107,39.972338219559;116.49206986996,39.972428072368;116.49275258215,39.972469542855;116.49411800653,39.970465106976;116.49629190586,39.972974098414;116.49642665169,39.973050127008;116.49635478725,39.973133067196;116.49529478674,39.970582610025;116.49581580394,39.970672465159;116.49563614284,39.971792188393;116.49640868558,39.972497189832;116.49235732773,39.965992927862;116.49550139701,39.969739348341;116.49674105862,39.970561874207;116.49641766863,39.970955853651;116.49748665219,39.971695422917;116.49721716054,39.971833659269;116.49740580469,39.97071393672;116.49746868608,39.971315271498;116.49866343241,39.971536450765;116.49891495795,39.971204681594;116.49392037931,39.963870786076;116.50048699259,39.971218505342;116.50090021313,39.971577921797;116.5010259759,39.971598657304;116.49411800653,39.963310861375;116.5014661456,39.971128650931;116.50199614585,39.971536450765;116.50199614585,39.971577921797;116.50199614585,39.971598657304;116.50274173942,39.97213086647;116.50335258717,39.972704541802;116.4942437693,39.962094218931;116.5018254678,39.970534226441;116.50203207807,39.970769232095;116.50202309501,39.970865998892;116.50346038383,39.972027189687;116.49286037881,39.959405085203;116.49347122656,39.960352170168;116.49412698958,39.961292329025;116.50451140128,39.971999542518;116.50488868959,39.972117042908;116.50457428266,39.970541138384;116.50522106263,39.970983501246;116.49325563324,39.958416507962;116.49578885478,39.96059412406;116.49586071922,39.961015813067;116.50566123233,39.96971170024;116.50574207983,39.970520402554;116.49435156596,39.958022455676;116.49564512589,39.959681607728;116.50233750194,39.965163434091;116.50238241722,39.965343158603;116.50563428316,39.968757833832;116.5063080123,39.968930636713;116.50631699535,39.968999757742;116.49465698983,39.957932583781;116.50240936638,39.964651907876;116.50231953583,39.964914583982;116.50571513066,39.967873076186;116.49634580419,39.95775975288;116.49754953357,39.958976473064;116.49779207606,39.959591738031;116.49796275411,39.959902824935;116.49819631354,39.959965042145;116.50407123158,39.964333930175;116.49640868558,39.957123731372;116.4975854658,39.958492552877;116.50467309627,39.964091989622;116.50579597816,39.965163434091;116.5061283512,39.965274033847;116.5062271648,39.965204909021;116.50643377507,39.965343158603;116.5071883517,39.966193387335;116.4931029213,39.9534180962;116.49366885377,39.954240819994;116.49665122806,39.956487703902;116.50336157022,39.961859183216;116.50354123133,39.962025090864;116.50397241797,39.962750932051;116.50421496046,39.962681804654;116.50551750345,39.963324686731;116.50522106263,39.963939912262;116.50545462206,39.964022863592;116.5060475037,39.964783246056;116.50624513091,39.964969884085;116.5075476739,39.965916891356;116.49365088766,39.953037842336;116.49683088917,39.955851670469;116.49720817748,39.956017592809;116.49719919443,39.956529184136;116.49897783934,39.957227430938;116.50019055177,39.958540945051;116.50015461955,39.95858242403;116.50020851788,39.958762165978;116.50443055378,39.96179005491;116.50471801154,39.961624146687;116.50531089318,39.962025090864;116.50528394402,39.962094218931;116.49364190461,39.952540052238;116.50061275536,39.957510875609;116.50450241822,39.961084942162;116.50481682515,39.96126467748;116.5050863168,39.961527366704;116.50505038458,39.961707100849;116.49436054901,39.95197312018;116.49787292356,39.955098101403;116.50368496021,39.958775992262;116.50523902874,39.960780773616;116.50593072398,39.960462777768;116.50592174093,39.960601037016;116.49466597289,39.951966206345;116.50319987523,39.957483222522;116.50301123108,39.958001716018;116.50352326522,39.957773579368;116.5036669941,39.957704446899;116.50350529911,39.957891104405;116.50365801104,39.958506379216;116.50364004493,39.95864464245;116.5042868249,39.958395768425;116.50497852014,39.958955733698;116.5049875032,39.959176953273;116.50558936789,39.959598651089;116.50643377507,39.960027259298;116.50643377507,39.960082563385;116.49471088816,39.951426925058;116.49490851538,39.951440752837;116.49511512564,39.951447666725;116.49796275411,39.952892653934;116.4983041102,39.953397355135;116.50255309527,39.956584491076;116.49765733024,39.952284242018;116.49853766964,39.952678327632;116.50300224802,39.955568218867;116.49985817874,39.953065497234;116.49997495845,39.952242759188;116.50028038233,39.952429431721;116.50151106087,39.952270414411;116.50045106037,39.951115799289;116.50163682365,39.950866897647;116.50194224752,39.950873811594;116.50247224777,39.951399269492;116.50265190887,39.951530633331;116.50151106087,39.950203155471;116.50778123333,39.952035344661;116.50775428417,39.952180534897;116.50807767415,39.952069913793;116.50841004719,39.952381035188;116.51250632032,39.954323783185;116.51243445588,39.95441365986;116.50730513141,39.951254077585;116.50770936889,39.951599772091;116.51181462507,39.952892653934;116.51322496472,39.952754378978;116.51317106639,39.952941050103;116.50505936764,39.947956063456;116.50558936789,39.948592170899;116.50558936789,39.948661312654;116.50611936814,39.948751196829;116.50637987674,39.948605999256;116.51333276139,39.951724221682;116.50709852115,39.948599085078;116.51362021915,39.951337044427;116.50323580745,39.945695068089;116.50411614685,39.946096106402;116.50785309777,39.947720978761;116.5080686911,39.947734807295;116.50283156997,39.945266369342;116.50455631655,39.945874844178;116.50805072499,39.946704573799;116.50795191138,39.947091777484;116.50810462332,39.947071034486;116.50832021664,39.946898175918;116.50722428392,39.94548763355;116.5166115765,39.946863604151;116.51713259369,39.947223149661;116.5174110684,39.947202406703;116.52007005271,39.94863365596;116.51638700012,39.946040790913;116.51824649252,39.946918918969;116.5183722553,39.947098691816;116.52253140981,39.946704573799;116.52351056281,39.947043377144;116.52369920697,39.947057205816;116.52395971557,39.946870518506;116.52660073377,39.947451321785;116.52352852892,39.9459439887;116.52372615614,39.945314770949;116.5183722553,39.94274943821;116.52355547809,39.944319073798;116.51915378109,39.942348380124;116.5216331043,39.94266646087;116.52171395179,39.942618057374;116.52193852817,39.942500505884;116.5221720876,39.942140935356;116.5221720876,39.942293061581;116.51671937316,39.940944658161;116.52289073201,39.942140935356;116.52308835922,39.941705299281;116.52326802033,39.9416983844;116.52238768093,39.940439864349;116.52302547784,39.940543589412;116.52326802033,39.940986147896;116.52354649503,39.941159021521;116.52371717308,39.941159021521;116.52459751248,39.940647314315;116.52734632734,39.941276575334;116.52520836023,39.940087197952;116.52565751298,39.94037071422;116.52590903852,39.939817510648;116.52426513944,39.93916057555;116.52541497049,39.939388774778;116.52707683569,39.938939290718;116.52728344596,39.938939290718;116.52617853018,39.937362615409;116.52740920873,39.937162070749;116.52819971758,39.937120578676;116.52957412501,39.937072171226;116.53025683719,39.937092917281;116.5271936154,39.936346055335;116.53224209237,39.935661424667;116.52704988652,39.934209154942;116.53194565155,39.935073604949;116.53578141608,39.933600575536;116.53245768569,39.932480221912;116.53350870314,39.932044523844;116.53579938219,39.933019653742;116.53670667075,39.93191312229;116.537398366,39.930993304297;116.53741633211,39.931311438246;116.53785650181,39.930910312587;116.53842243428,39.930301703615;116.53858412927,39.930059641713;116.53886260398,39.929748417999;116.53887158703,39.929630844224;116.53894345147,39.929859075483;116.53895243453,39.929948984555;116.53613175523,39.928275273065;116.5374971796,39.928441262824;116.53839548511,39.929174379407;116.53850328177,39.928904648754;116.53465853419,39.927666640478;116.53478429696,39.927445318185;116.53602395857,39.928206110546;116.53435311032,39.926829761765;116.53460463586,39.926276447862;116.53202649905,39.925833793494;116.53261938068,39.925653964333;116.53172107517,39.924208397242;116.53049039663,39.923406059647;116.53213429571,39.923046387993;116.53226005848,39.923053304774;116.53283497401,39.923634311824;116.53306853344,39.92335764242;116.53480226307,39.923295391649;116.53508073778,39.92334380892;116.52987954888,39.922257870396;116.53038259996,39.922555294776;116.5304364983,39.922285537836;116.53080480355,39.922050364244;116.53090361716,39.921669934653;116.52538802133,39.921939694037;116.53010412526,39.920992073009;116.53021192192,39.92128258597;116.53022090497,39.92116499754;116.52502869913,39.920992073009;116.52588208936,39.920341872831;116.52671751348,39.920258868105;116.52897226031,39.920037521674;116.52952022668,39.920604720461;116.52696903903,39.919933765286;116.52700497125,39.919933765286;116.52802005647,39.919587909514;116.52832548035,39.919352726584;116.5284153109,39.919373478052;116.52854107367,39.918612586755;116.52909802309,39.919345809427;116.52918785364,39.918840855039;116.5285141245,39.91825980699;116.52864887033,39.917519655254;116.52743615789,39.9166549818;116.52802005647,39.916620394633;116.52887344671,39.916751825774;116.52641208961,39.9166549818;116.507727335,39.920286536359;116.50844597941,39.919899179788;116.50893106439,39.919435732417;116.52413937667,39.916060080073;116.52423819028,39.915769544778;116.52436395305,39.915382162453;116.52717564929,39.914711155698;116.50939818325,39.918999950662;116.50959581046,39.918972281885;116.50986530212,39.918425821225;116.51012581071,39.918481159214;116.51015275988,39.918411986721;116.51026055654,39.918287476057;116.51034140404,39.918287476057;116.50939818325,39.91778943112;116.50951496297,39.917595745992;116.50985631906,39.918031536754;116.50984733601,39.917996950288;116.51067377708,39.917671836644;116.5113295401,39.917491985874;116.51153615037,39.917270630428;116.51177869285,39.917007769898;116.51236259143,39.91698010031;116.51238055754,39.916924761099;116.51243445588,39.916841752198;116.51306326973,39.916890174069;116.51715954286,39.915811049896;116.52040242575,39.915126212204;116.52086954461,39.914386026331;116.52169598568,39.914386026331;116.52152530764,39.913943294478;116.52281886757,39.913970965304;116.51139242148,39.916827917371;116.51975564578,39.91424075526;116.52077073101,39.913825693345;116.50972157324,39.916246852106;116.5108085229,39.916212264731;116.51440174494,39.914130072331;116.51507547407,39.914635061731;116.51502157574,39.914420614636;116.5079878436,39.91578337982;116.50888614911,39.915306069236;116.50916462382,39.915520513537;116.50968564101,39.915575853891;116.51355733776,39.914268425964;116.51338665972,39.913977883008;116.51440174494,39.913915623642;116.51415920245,39.913313780158;116.50829326747,39.91490484905;116.50722428392,39.914891013829;116.50443953684,39.914434449953;116.50905682716,39.912566656694;116.510009031,39.912525149594;116.51008987849,39.912635835137;116.51032343793,39.912559738845;116.51047614986,39.912718849177;116.50435868934,39.913922541352;116.50489767265,39.913555901741;116.50233750194,39.913887952794;116.50354123133,39.913908705931;116.503487333,39.913590490468;116.50643377507,39.912518231741;116.50758360612,39.911556643396;116.50277767164,39.913299944613;116.50315495996,39.913286109065;116.50594869009,39.911729591944;116.50643377507,39.911058549119;116.50649665645,39.911058549119;116.50551750345,39.910733402275;116.50643377507,39.910691894055;116.50643377507,39.910339073163;116.50572411372,39.910090022019;116.50485275737,39.909785624936;116.50373885854,39.90883783438;116.50506835069,39.90858185948;116.49619309225,39.912559738845;116.5021668239,39.908367393282;116.49480970177,39.912462888896;116.4989059749,39.907959213809;116.49966055152,39.907412664574;116.50010072122,39.906741579122;116.50023546705,39.906831518794;116.50010072122,39.906554780962;116.49431563374,39.909965496104;116.49772021162,39.907461093165;116.49825919493,39.90766172553;116.49773817773,39.907281215368;116.49833105937,39.906451003984;116.49832207631,39.90539938834;116.49832207631,39.905247179464;116.49832207631,39.905122644676;116.49860055102,39.905088051639;116.49755851663,39.90480438807;116.49823224576,39.904866655784;116.49425275235,39.906783089755;116.4950432612,39.905129563281;116.49505224426,39.905088051639;116.4975046183,39.903524427977;116.49319275185,39.90656861788;116.49521393925,39.904264732159;116.49555529534,39.90432008168;116.49605834643,39.903552103044;116.49635478725,39.903434483929;116.49622902448,39.903344539762;116.49643563474,39.903344539762;116.49481868482,39.904084845903;116.49639071947,39.902154498039;116.49445936262,39.902742602657;116.49604038032,39.901746281254;116.4940641082,39.902154498039;116.49425275235,39.901946930488;116.49617512614,39.899331525047;116.49244715828,39.901933092629;116.4936239385,39.901344981007;116.49376766738,39.900971354511;116.49392037931,39.900611564092;116.49177342915,39.901524874514;116.49278851437,39.900120308714;116.4926627516,39.899836624414;116.49271664993,39.899836624414;116.49191715803,39.899366121014;116.49219563274,39.899310767458;116.48906952956,39.900424749085;116.48928512288,39.899248494655;116.48942885176,39.899144706522;116.48934800427,39.898847179663;116.48967139425,39.898964806717;116.48895274984,39.898432023731;116.48650935886,39.898272879952;116.48712918966,39.897456397312;116.48712918966,39.897352606443;116.48729986771,39.897387203417;116.48668901996,39.896778294107;116.48668901996,39.896695260596;116.48543139225,39.896674502203;116.48546732447,39.896549951709;116.48468579867,39.895608896161;116.48445223924,39.895691930998;116.48323054375,39.896543032231;116.48389528982,39.894653988246;116.48405698482,39.894653988246;116.48404800176,39.894460237177;116.48166749216,39.897075830019;116.48262867905,39.896245493986;116.48262867905,39.896044827924;116.48239511962,39.895601976586;116.48303291653,39.895332112638;116.4830598657,39.894640148902;116.48513495143,39.890432857823;116.48522478198,39.890114532445;116.48112850885,39.897636301109;116.48067037304,39.897297251249;116.48120037329,39.896716018983;116.48383240844,39.89135322499;116.48400308648,39.89083422248;116.48409291704,39.89084114254;116.48421867981,39.89082730242;116.48468579867,39.890197573992;116.48046376278,39.89754634927;116.48371562872,39.890342896454;116.48398512037,39.88949863781;116.48371562872,39.889124946211;116.4833203743,39.888066142196;116.48370664567,39.888024620134;116.48191003465,39.887941575934;116.4816585091,39.887844690906;116.48196393298,39.887900053796;116.4816585091,39.887782407601;116.48091291553,39.88732566162;116.48085003414,39.886792787431;116.48014037279,39.886419080965;116.47985291503,39.886183783247;116.47975410142,39.886045372444;116.47886477897,39.886612854944;116.47908037229,39.886356796354;116.47855037204,39.885145695363;116.47809223623,39.884882710584;116.47809223623,39.884661248928;116.47758918514,39.885436361568;116.47734664266,39.884917313902;116.47772393097,39.884398262276;116.47605308272,39.886073054628;116.47656511686,39.885450202784;116.47656511686,39.885118012803;116.47659206603,39.884986520487;116.47584647245,39.88586543798;116.47588240467,39.88370618728;116.47615189633,39.883713108065;116.4763764727,39.883277097246;116.47595426912,39.882944896651;116.47596325217,39.882585010843;116.47656511686,39.882668061583;116.47507392972,39.882204360319;116.47535240442,39.882211281257;116.47460681085,39.881844470593;116.47436426836,39.881449973897;116.47316053898,39.884896551913;116.47394206477,39.882986421814;116.47372647145,39.881899838367;116.47406782754,39.881837549618;116.4742564717,39.881477657951;116.47245087763,39.88462664548;116.47243291152,39.883450117747;116.47242392846,39.882377383548;116.47250477596,39.8822597278;116.47291799649,39.881844470593;116.47164240267,39.884495152214;116.47156155517,39.884107591635;116.47144477546,39.883041788659;116.47144477546,39.882986421814;116.47222630125,39.882716507801;116.47206460626,39.881699129971;116.47228019958,39.881470736938;116.47237003013,39.881470736938;116.47139087712,39.883463959368;116.47112138547,39.88342935531;116.47057341911,39.883297859729;116.46998053747,39.884100670891;116.47013324941,39.882965659236;116.47078901243,39.88072326347;116.46963918138,39.882965659236;116.46825579089,39.880252627813;116.4685342656,39.879906570106;116.46859714699,39.879442850018;116.46829172311,39.879055260654;116.46844443505,39.878252389948;116.46821985867,39.879055260654;116.46795935008,39.878847622587;116.46795036702,39.878806094897;116.46790545175,39.877082673426;116.46790545175,39.876971929992;116.46771680759,39.876342073279;116.4675551126,39.87606521134;116.46689934957,39.881560710043;116.46692629874,39.881353079622;116.4666747732,39.880771711073;116.46708799373,39.8789514417;116.46655799348,39.878570770844;116.46629748488,39.880674815832;116.46640528154,39.879961939457;116.46578545074,39.879941175956;116.46506680633,39.879325189195;116.46556985742,39.879055260654;116.46616273906,39.878612298678;116.46640528154,39.877304159755;116.4639529075,39.881574552048;116.46393494139,39.881477657951;116.46398883972,39.880474103822;116.4635127378,39.88121465899;116.46221917787,39.881491499973;116.46220121176,39.881083159128;116.46220121176,39.880944737946;116.46264138146,39.880550236033;116.46203951677,39.882841083633;116.46203951677,39.882591931741;116.46129392319,39.88222512313;116.46197663538,39.882003652822;116.46136578763,39.881775260812;116.46127595708,39.881408447796;116.46197663538,39.881020869631;116.46118612653,39.887927735224;116.46117714348,39.887429467794;116.46106934681,39.887228775714;116.46110527904,39.887208014431;116.46102443154,39.885380996672;116.46104239765,39.881927522237;116.46062019406,39.885249504864;116.46003629548,39.885055727;116.45976680383,39.884322134371;116.45943443079,39.884356737975;116.45842832862,39.885602455984;116.45815883696,39.8853948379;116.45752104005,39.885021123752;116.45713476868,39.886183783247;116.45674849731,39.885360234825;116.4562903615,39.886031531349;116.4554100221,39.886972719442;116.45542798821,39.886509047524;116.45541900516,39.88638447841;116.45640714122,39.893401516231;116.45640714122,39.893311558789;116.45464646242,39.88745022901;116.45547290349,39.89309704441;116.45483510658,39.892536535902;116.45498781851,39.892467337;116.45320019055,39.888453680219;116.45320019055,39.888246070838;116.45385595357,39.888059221854;116.45435900466,39.894107332027;116.45415239439,39.894114251753;116.45438595382,39.892723372585;116.45374815691,39.892737212319;116.45345171609,39.891872223539;116.45320019055,39.88971316354;116.45296663111,39.888370636543;116.45230188504,39.888156106577;116.45256239364,39.88760939812;116.45376612302,39.894923854886;116.45311934305,39.892633414246;116.45268815641,39.890592019953;116.45217612227,39.889090345033;116.45356849581,39.895117604633;116.45306544472,39.894923854886;116.4532091736,39.894820060151;116.4525893428,39.89237045842;116.45166408813,39.890716581361;116.45198747811,39.890439777924;116.45175391868,39.890149133102;116.45116103704,39.889041903354;116.45249951225,39.895491263301;116.45158324063,39.892411977828;116.45147544397,39.891007223757;116.45104425732,39.890453618122;116.45118798621,39.890370576888;116.45070290123,39.890239094727;116.45225696976,39.895207559685;116.45085561317,39.892142101219;116.45040646041,39.892211300452;116.45057713846,39.892149021146;116.45054120624,39.892135181292;116.45353256359,39.901165087025;116.45176290173,39.896003310733;116.4513496812,39.896812891373;116.45293968195,39.902853304134;116.45194256283,39.901005949643;116.45222103754,39.900853730929;116.4521491731,39.900784540492;116.45198747811,39.900154904279;116.45147544397,39.899732837179;116.45148442702,39.899580615614;116.45125086759,39.899449151262;116.44962493462,39.894930774529;116.44925662936,39.89361602965;116.45131374898,39.899732837179;116.45087357928,39.899352282629;116.45081069789,39.899352282629;116.45051425707,39.898355911536;116.44866374772,39.893892820158;116.44803493386,39.893083204749;116.4480079847,39.892792571226;116.45187069839,39.903448321482;116.45193357978,39.903323783398;116.45193357978,39.902777196888;116.44838527301,39.896307769541;116.44838527301,39.896155540307;116.4547901913,39.910290646623;116.45471832686,39.910283728543;116.45151137619,39.903669721957;116.44731628946,39.895172961602;116.44681323837,39.894674747256;116.44725340807,39.894474076558;116.45105324038,39.903967227709;116.44672340782,39.895145283123;116.45091849455,39.904659096516;116.45048730791,39.904154032981;116.45037052819,39.903994902596;116.45041544347,39.903745828203;116.44597781425,39.895193720454;116.45312832611,39.909930905532;116.45301154639,39.909591916992;116.4455466276,39.896058666982;116.44553764455,39.8959410349;116.44507950874,39.897477155467;116.44481900014,39.896224735456;116.44446866099,39.896148620789;116.44409137268,39.896383884029;116.44409137268,39.896114023185;116.44307628745,39.895712689691;116.4493284938,39.905987464883;116.44435188127,39.89825212204;116.44208815139,39.894999970924;116.44724442502,39.903503671668;116.44673239088,39.903337620975;116.44657967894,39.902984761903;116.44286069413,39.897677817302;116.44648984839,39.903420646372;116.44176476141,39.897366445235;116.44195340556,39.897214218372;116.44673239088,39.905330202529;116.44663357727,39.90521258649;116.44394764379,39.901863903291;116.44215103277,39.898369750123;116.44154018503,39.897871559202;116.44110899838,39.897138104813;116.44578018703,39.90528177242;116.44435188127,39.902957086604;116.44068679479,39.898556570777;116.44595984814,39.905689967973;116.44546578011,39.905710723614;116.44534900039,39.905772990498;116.44508849179,39.905357876862;116.44413628795,39.903420646372;116.44394764379,39.903136975845;116.44325594855,39.902479685927;116.44176476141,39.901095896905;116.44054306591,39.898992483641;116.44056103202,39.898888695117;116.44012086232,39.898715713893;116.442186965,39.901953849417;116.44212408361,39.901953849417;116.44037238786,39.8998504627;116.44011187927,39.899753594638;116.44011187927,39.899642888114;116.43970764179,39.899608292288;116.43989628594,39.899345363436;116.43965374346,39.899449151262;116.43976154012,39.899283090664;116.44199832084,39.903600534386;116.4391057771,39.89955293893;116.44507950874,39.907786255666;116.44330086383,39.905876768511;116.4433457791,39.905523922621;116.44423510156,39.907620215434;116.44311221967,39.906658557781;116.44195340556,39.904728283009;116.44180967668,39.904762876229;116.44385781324,39.907613297082;116.44028255731,39.906347226848;116.44028255731,39.906319552919;116.43995916733,39.906091242568;116.44261815164,39.90952273545;116.44285171107,39.909232172202;116.43940221791,39.906361063809;116.44235764304,39.910007004768;116.44021069287,39.907329644053;116.4395459468,39.906679313126;116.43907882793,39.906589373253;116.43837814963,39.906610128618;116.43817153937,39.906693150019;116.43827035297,39.90651327019;116.43683306416,39.906693150019;116.43623119946,39.906444085513;116.43597967392,39.907198194686;116.43515323285,39.906852274086;116.43385068986,39.906741579122;116.43388662208,39.90666547623;116.43354526599,39.908671796717;116.4268798391,39.907765500659;116.42990712867,39.91012461251;116.42975441674,39.910207629617;116.42956577258,39.910207629617;116.42699661882,39.907938458855;116.42909865371,39.910373663527;116.42858661957,39.910166121076;116.42844289069,39.910166121076;116.4274008563,39.909917069298;116.42684390688,39.909391290325;116.42649356774,39.908941607713;116.42654746607,39.908616450739;116.42684390688,39.910415171942;116.42656543218,39.909799461197;116.42592763526,39.910034677196;116.4260803472,39.910498188694;116.42527187224,39.909979332328;116.42467000755,39.910096940118;116.4248406856,39.909785624936;116.42584678777,39.91096169703;116.42408610897,39.910173039168;116.42369085454,39.910449762267;116.42389746481,39.911695002269;116.4237806851,39.911611986979;116.42362797316,39.91107930312;116.42338543067,39.911328350639;116.42434661757,39.912158502442;116.42413102424,39.911847196705;116.42365492232,39.912213845535;116.42311593902,39.912089323513;116.42349322733,39.911591233141;116.42302610847,39.911971719171;116.42293627792,39.911840278783;116.42274763376,39.911535889541;116.42256797266,39.911418284241;116.42181339603,39.912123912986;116.42151695521,39.912808780938;116.42050186998,39.913030150921;116.42008864945,39.913424464417;116.42018746306,39.912898712581;116.41900169978,39.914123154641;116.41914542866,39.913798022461;116.41791475012,39.912898712581;116.42429271924,39.916800247709;116.42261288793,39.915804132378;116.42261288793,39.915741874685;116.42193017575,39.915970152614;116.42187627741,39.915977070115;116.42193017575,39.915880225037;116.42148102299,39.91579721486;116.42060068359,39.915340657072;116.41964847975,39.914932519484;116.41907356422,39.915008613118;116.41908254728,39.914780331959;116.41874119118,39.914296096657;116.4184986487,39.914448285267;116.41674695295,39.914164660765;116.42383458343,39.91747815118;116.42306204069,39.917146117672;116.42269373543,39.917173787193;116.42252305738,39.917014687294;116.42225356573,39.916841752198;116.42184034519,39.916793330292;116.42181339603,39.916744908352;116.42029525972,39.916426706171;116.42004373417,39.915769544778;116.42005271723,39.915686534466;116.42004373417,39.915638111737;116.42000780195,39.91561044159;116.41721407182,39.914711155698;116.41626186798,39.914697320438;116.41613610521,39.91424075526;116.41588457966,39.914150825394;116.4156779694,39.91444136761;116.41563305412,39.914386026331;116.42380763426,39.917706423275;116.42380763426,39.917678753971;116.41618102048,39.915617359128;116.42528983835,39.918951530295;116.42438254979,39.919145211558;116.42431068535,39.919152128736;116.42420288869,39.919152128736;116.42311593902,39.91825980699;116.41459101973,39.915624276665;116.41422271447,39.915700369525;116.41379152782,39.916177677339;116.41320762924,39.915963235112;116.42919746732,39.920992073009;116.42641272024,39.920660056674;116.42570305889,39.920328038717;116.41516593525,39.916917843694;116.41499525721,39.917146117672;116.41413288392,39.917090778596;116.41392627365,39.916904008883;116.41309983258,39.916108502501;116.41270457816,39.916592724886;116.41253390011,39.916876339252;116.42820933126,39.921697602331;116.4282003482,39.921614599262;116.42707746632,39.921019740963;116.42615221164,39.920888318079;116.41432152808,39.917782513804;116.41159067933,39.91743664708;116.41040491605,39.917325969357;116.42707746632,39.921856691264;116.42708644937,39.921808272932;116.42829916181,39.922645213518;116.41124034018,39.919221300474;116.41105169602,39.919221300474;116.41050372966,39.91920054896;116.41046779744,39.918536497157;116.40957847498,39.919145211558;116.40947966138,39.918474241968;116.41048576355,39.919380395206;116.40998271246,39.919906096889;116.40946169527,39.920998989998;116.40455694718,39.9191313772;116.40628169376,39.921033574936;116.40570677823,39.921310253806;116.40682067707,39.92202269671;116.40647033792,39.921891275765;116.40789864368,39.92301180408;116.40543728658,39.924588812617;116.4052127102,39.924249897205;116.40464677773,39.923980146994;116.40446711663,39.923765729396;116.4043323708,39.923578978033;116.40357779418,39.924166897254;116.40320050586,39.924153063919;116.40249084451,39.923502893997;116.40232016646,39.923703478999;116.40223931897,39.923703478999;116.40183508149,39.923412976391;116.39962524993,39.923226224058;116.39897846997,39.922984136937;116.40604813433,39.92498305903;116.40355982807,39.924609562485;116.40073914876,39.924865477006;116.40703627039,39.926387111003;116.40686559234,39.926497773964;116.40644338875,39.926490857534;116.4063535582,39.926338695901;116.40437728608,39.926407860322;116.40408982832,39.926366361678;116.39949948716,39.926207283307;116.39755914726,39.925764628488;116.39752321504,39.925764628488;116.39746931671,39.925764628488;116.40621881238,39.927362322139;116.4046737269,39.926892009297;116.40034389434,39.928275273065;116.39788253724,39.927756552454;116.39647219759,39.929423360597;116.39570863791,39.929119050129;116.39543914626,39.929063720807;116.39519660377,39.929119050129;116.39491812906,39.929001475265;116.39472050185,39.928745576329;116.39329219609,39.928752492529;116.39548406153,39.929637760334;116.39919406329,39.931996112775;116.40175423399,39.934167661065;116.40103558958,39.93391869727;116.40049660628,39.93359365983;116.39996660603,39.934057010602;116.39893355469,39.933413851216;116.40011931796,39.934361298941;116.39997558908,39.934520358212;116.39975999576,39.93499753379;116.40352389585,39.935896551129;116.40105355569,39.935938043949;116.40055050461,39.935931128481;116.40571576129,39.936850879587;116.40354186196,39.936795556564;116.4030118617,39.936871625709;116.40117931846,39.936933864036;116.40650627014,39.937417937969;116.4046737269,39.938047228922;116.40271542089,39.938206279559;116.41508508776,39.937376446053;116.41455508751,39.937618481873;116.41396220587,39.938614277313;116.4130369512,39.938607362117;116.41288423926,39.939070678674;116.41274051038,39.939119084699;116.4125967815,39.939188236104;116.41222847624,39.939139830128;116.41212966263,39.939063763525;116.40864423725,39.939838255863;116.40606610044,39.940287733971;116.40607508349,39.940308479043;116.40426050636,39.939727614641;116.40412576054,39.93982442572;116.41221051013,39.939845170933;116.41212067958,39.939845170933;116.41151881488,39.939769105121;116.4080154234,39.940107943085;116.40807830478,39.940495184402;116.40686559234,39.941207426057;116.40557203241,39.941449448219;116.41307288342,39.940585079392;116.41519288442,39.941304235025;116.41410593475,39.941290405181;116.41498627415,39.942376039379;116.41501322332,39.942652631303;116.41461796889,39.942030297888;116.41418678225,39.943109005515;116.41341423951,39.943226555951;116.41337830729,39.943115920252;116.41279440871,39.943440912105;116.41208474736,39.944132378956;116.41286627315,39.944837667887;116.41320762924,39.945529120508;116.4162978002,39.945556778467;116.41538152858,39.946234394925;116.4152377997,39.946275881428;116.41488746055,39.946317367905;116.41478864694,39.946303539082;116.4161181391,39.946656173183;116.41580373217,39.94625513818;116.41496830804,39.947098691816;116.41495932499,39.947195492382;116.41492339277,39.948253375286;116.41690864794,39.948170404673;116.41490542666,39.948937878966;116.41878610646,39.948066691266;116.41870525896,39.94803903433;116.41486949444,39.949684602379;116.41739373292,39.949477180033;116.41785186873,39.950341435627;116.4198191578,39.951171110641;116.42190322658,39.951751877116;116.42305305763,39.952277328215;116.42380763426,39.952768206486;116.4236998376,39.952768206486;116.4236998376,39.952975618773;116.42075339553,39.955429949362;116.42077136164,39.955540564988;116.42496644837,39.953729211413;116.42707746632,39.953494146717;116.42676305939,39.954019584324;116.42630492358,39.954337610373;116.4261611947,39.954330696779;116.42581085555,39.954468968524;116.42522695697,39.95442748703;116.42498441448,39.954226992786;116.42495746531,39.954690202729;116.42417593952,39.955381554969;116.42303509152,39.955906977961;116.42627797441,39.954669462052;116.42562221139,39.95489760914;116.42415797341,39.955720314996;116.43070662058,39.953335131902;116.42988916256,39.953300563415;116.42961967091,39.953895138943;116.42933221315,39.953708470443;116.42911661982,39.953853657098;116.4282811957,39.954247733597;116.4260803472,39.956301042534;116.42525390613,39.956294129141;116.43075153585,39.954233906391;116.42821831431,39.955678834267;116.42637678802,39.956321782712;116.42620610997,39.95663979797;116.42603543193,39.956971638389;116.43192831607,39.95402649795;116.43104797667,39.954392919099;116.43104797667,39.954503536416;116.42882916206,39.955796362932;116.42728407658,39.956653624686;116.426700178,39.957075338187;116.43200916357,39.954724770508;116.43183848552,39.95482847374;116.43169475664,39.95482847374;116.4282003482,39.957497049067;116.42736492408,39.957503962338;116.42777814461,39.957863451474;116.43060780697,39.956819545065;116.42977238285,39.957365696779;116.42823628043,39.958146893487;116.4282003482,39.958748339691;116.43170373969,39.956432396884;116.43058085781,39.957282737308;116.42997001006,39.957939497008;116.42988017951,39.958181459505;116.43368899487,39.95575488225;116.44040832009,39.951731135542;116.43534187701,39.955575132334;116.43168577358,39.958388855245;116.4316228922,39.958934994326;116.43109289195,39.958990299304;116.43076950196,39.959059430463;116.42989814562,39.959785303383;116.44033645564,39.951945464836;116.43135340054,39.959557172731;116.43071560363,39.960227736401;116.43282662158,39.959978868184;116.43163187525,39.960905206368;116.43109289195,39.960580298147;116.43989628594,39.954019584324;116.43288051991,39.960352170168;116.43280865547,39.96049042964;116.43183848552,39.960967422658;116.43169475664,39.96191448581;116.43988730289,39.955022052683;116.43378780848,39.961382196469;116.43390458819,39.961693275163;116.43302424879,39.962280864359;116.43465018177,39.961866096043;116.43387763903,39.963020528228;116.441046117,39.956252648763;116.43383272375,39.963331599409;116.43639289446,39.962336166609;116.43641086057,39.962529724131;116.43520713118,39.963559717368;116.43465916482,39.963739446129;116.43596170781,39.964188765947;116.44089340506,39.959501868215;116.44066882868,39.959612477202;116.43737204746,39.963428376819;116.43751577634,39.96352515409;116.43696780998,39.96352515409;116.44252832109,39.958195285908;116.44119882893,39.959792216422;116.44289662635,39.959239171148;116.44262713469,39.959356693646;116.44069577785,39.961119506683;116.44092933728,39.96135454496;116.44037238786,39.962177172518;116.43874645489,39.963697970303;116.43865662434,39.96430627987;116.43862069212,39.96430627987;116.43856679379,39.964299367292;116.43749781023,39.965529795091;116.43723730164,39.96543302068;116.44318408411,39.959183866373;116.443166118,39.959716172964;116.44313916884,39.960054911347;116.44255527025,39.960386735062;116.4379649291,39.965903066527;116.44331882994,39.959930477036;116.44309425356,39.960455864799;116.44307628745,39.960538820389;116.44307628745,39.960677079482;116.44209713444,39.962045829291;116.43819848853,39.966856973087;116.44067781174,39.965543619996;116.44012984538,39.965598919586;116.44012984538,39.965778642943;116.4396447604,39.966262511154;116.43929442125,39.967078166894;116.4444057796,39.961001987239;116.4440464574,39.961001987239;116.44394764379,39.961361457839;116.44260018553,39.96392608703;116.44132459171,39.965142696617;116.44092035423,39.965543619996;116.4409652695,39.965605832032;116.44071374396,39.965598919586;116.43969865873,39.96710581607;116.4445674746,39.961561930999;116.44445967794,39.961651798086;116.44018374371,39.968322368621;116.43598865698,39.975130512737;116.43536882617,39.975130512737;116.4356832331,39.975441528374;116.43537780923,39.975559022799;116.44498967819,39.962197910899;116.43864764129,39.972649248005;116.43657255556,39.974957725655;116.43597069087,39.975669605602;116.44542984789,39.962419119901;116.445447814,39.962495160329;116.44050713369,39.970022740732;116.44037238786,39.971024972616;116.44003103177,39.972034101477;116.43989628594,39.972144690029;116.43898899738,39.973070862065;116.43846798018,39.973444091996;116.43868357351,39.973609971306;116.43869255656,39.973679087565;116.43842306491,39.974335688515;116.4380637427,39.974349511625;116.43798289521,39.97434260007;116.43807272576,39.974764203601;116.43790204771,39.975013017569;116.43768645439,39.975966795989;116.44604967869,39.962840797563;116.44620239062,39.962909924798;116.44088442201,39.971819835646;116.44043526925,39.971895865535;116.44061493035,39.97269763008;116.44740612001,39.96191448581;116.44740612001,39.962149521333;116.44737018779,39.962356904942;116.44732527251,39.96242603267;116.44672340782,39.962757844787;116.44100120172,39.972718365244;116.43851289546,39.978164582137;116.43980645539,39.976941294865;116.43936628569,39.978406472486;116.44366916909,39.97232439604;116.44139645615,39.976561172856;116.44136950698,39.976561172856;116.4407856084,39.977763733372;116.4407856084,39.97779137819;116.44418120323,39.972746012119;116.44176476141,39.976782335012;116.44176476141,39.976927472284;116.44103713394,39.977687710063;116.44079459145,39.978005625151;116.44103713394,39.978599984144;116.44048018453,39.978869517319;116.44021967593,39.97981633049;116.43983340456,39.9806940214;116.44167493085,39.978848784036;116.44207018528,39.979028472279;116.44462137293,39.975925327641;116.4436062877,39.978005625151;116.44320205022,39.978461761588;116.44482798319,39.977314503491;116.44464832209,39.977756822165;116.44402849129,39.978019447513;116.44397459296,39.978019447513;116.44393866074,39.97876585084;116.44393866074,39.978800406351;116.44527713595,39.977293769732;116.44481001708,39.978254427224;116.44652578061,39.97799871397;116.44615747535,39.978054003404;116.44557357677,39.978669095317;116.44551967844,39.97867600643;116.45052324013,39.977259213454;116.45031662986,39.977369793483;116.45019086709,39.97743199467;116.45010103654,39.977749910958;116.44962493462,39.977991802787;116.4502088332,39.978164582137;116.44981357877,39.978468672722;116.45013696876,39.978551606281;116.45019985014,39.978599984144;116.45065798595,39.978696739766;116.45176290173,39.978689828655;116.45207730866,39.978599984144;116.45260730891,39.979249626385;116.45313730916,39.978703650877;116.4532900211,39.978904072777;116.45346069915,39.979118316222;116.45298459722,39.979284181649;116.45473629297,39.976028998464;116.45468239464,39.976277807791;116.45467341158,39.977597864224;116.45460154714,39.978420294766;116.4539098519,39.978966272556;116.45520341183,39.976678665341;116.45573341209,39.977072609245;116.45499680157,39.977245390938;116.45521239489,39.977819022997;116.45484408963,39.979076849801;116.4559310393,39.976574995512;116.45573341209,39.979415491492;116.45556273404,39.979961461268;116.45549985265,39.980009838124;116.45586815791,39.980148057525;116.45703595507,39.975835479467;116.45754798922,39.975911504853;116.45629934456,39.979152871553;116.45627239539,39.979443135637;116.45840137945,39.975075220919;116.45766476893,39.977570219326;116.45747612477,39.977708443701;116.45722459923,39.979180515805;116.45956917661,39.971819835646;116.45920087135,39.97198571893;116.45964104105,39.972863511216;116.45933561718,39.974225103537;116.4586708711,39.975531377071;116.45850917611,39.978219871435;116.45885951526,39.978302805299;116.459632058,39.97399010986;116.45952426134,39.974093783642;116.45978476994,39.974328776959;116.45948832912,39.974356423178;116.45953324439,39.974425538677;116.45922782052,39.977853578991;116.45912900691,39.977867401383;116.45888646443,39.978862606225;116.46053036351,39.973174537252;116.46089866877,39.975102866833;116.45997341409,39.978475583856;116.46132087236,39.974411715583;116.4613927368,39.974701999966;116.46115917737,39.975337856654;116.46123104181,39.976492059535;116.46108731292,39.97774299975;116.46229104231,39.97634692133;116.46162629623,39.976962028731;116.46301866977,39.974114518379;116.46259646618,39.975496819894;116.46370138196,39.975026840541;116.465174603,39.974840230188;116.46515663689,39.974888610699;116.46534528104,39.976222516908";
        String[] split = str.split(";");
        List<double[]> coordinate = new ArrayList<>();
        for (String s : split) {
            String[] split1 = s.split(",");
            double[] c = {Convert.toDouble(split1[1]), Convert.toDouble(split1[0])};
            coordinate.add(c);
        }
        System.out.println(coordinate.size());
        List<double[]> doubles = douglasPeucker(coordinate, 501);

        Point2D.Double point = new Point2D.Double();
        point.setLocation(40.079651,116.688564);
        List<Point2D.Double> pts = new ArrayList<>();
        for (double[] d : doubles) {
            Point2D.Double p = new Point2D.Double();
            p.setLocation(d[0],d[1]);
            pts.add(p);
        }
        System.out.println(isPtInPoly(point, pts));
    }

}


